#pragma once

#include <algorithm>
#include <iostream>
#include <numeric>
#include <random>
#include <vector>

namespace sa {
constexpr size_t N = 10;

std::vector<int> genSortedVec()
{
    std::vector<int> ret(N);
    std::iota(ret.begin(), ret.end(), 0);
    return ret;
}

std::vector<int> genRandomVec(int seed = -1)
{
    auto ret = genSortedVec();
    std::random_device rd;
    unsigned s = seed < 0 ? rd() : seed;
    std::mt19937 g(s);
    std::shuffle(ret.begin(), ret.end(), g);
    return ret;
}

template <typename T>
std::ostream& operator<<(std::ostream& os, const std::vector<T>& vec)
{
    for (const auto& v : vec)
        os << v << " ";
    return os;
}

using SortFunc = void(std::vector<int>&);

bool testSortOnce(std::vector<int>& vec, SortFunc sort)
{
    static const std::vector<int> ref = genSortedVec();
    sort(vec);
    if (vec.size() != ref.size())
        return false;
    for (size_t i = 0; i < ref.size(); ++i)
        if (ref[i] != vec[i])
            return false;
    return true;
}

void testSort(SortFunc sort)
{
    for (int i = 0; i < 100; ++i) {
        auto vec = genRandomVec(i);
        auto org = vec;
        if (!testSortOnce(vec, sort)) {
            std::cout << "\33[31m";
            std::cout << "test failed with seed: " << i << '\n';
            std::cout << "origin: " << org << '\n';
            std::cout << "result: " << vec << '\n';
            std::cout << "\33[0m";
            return;
        }
    }
    std::cout << "all test passed" << '\n';
}

#define TEST_SORT(func)             \
    {                               \
        std::cout << #func << ": "; \
        testSort(func);             \
    }

} //namespace sa
